Search Results

Documents authored by Lee, James R.

Document
DOI: 10.4230/LIPIcs.ITCS.2022.60
Multiscale Entropic Regularization for MTS on General Metric Spaces

Authors: Farzam Ebrahimnejad and James R. Lee

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We present an O((log n)²)-competitive algorithm for metrical task systems (MTS) on any n-point metric space that is also 1-competitive for service costs. This matches the competitive ratio achieved by Bubeck, Cohen, Lee, and Lee (2019) and the refined competitive ratios obtained by Coester and Lee (2019). Those algorithms work by first randomly embedding the metric space into an ultrametric and then solving MTS there. In contrast, our algorithm is cast as regularized gradient descent where the regularizer is a multiscale metric entropy defined directly on the metric space. This answers an open question of Bubeck (Highlights of Algorithms, 2019).
Cite as

Farzam Ebrahimnejad and James R. Lee. Multiscale Entropic Regularization for MTS on General Metric Spaces. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.60,
  author =	{Ebrahimnejad, Farzam and Lee, James R.},
  title =	{{Multiscale Entropic Regularization for MTS on General Metric Spaces}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{60:1--60:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.60},
  URN =		{urn:nbn:de:0030-drops-156568},
  doi =		{10.4230/LIPIcs.ITCS.2022.60},
  annote =	{Keywords: Metrical task systems, online algorithms, metric embeddings, convex optimization}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ITCS.2021
LIPIcs, Volume 185, ITCS 2021, Complete Volume

Authors: James R. Lee

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
LIPIcs, Volume 185, ITCS 2021, Complete Volume
Cite as

12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 1-1550, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Proceedings{lee:LIPIcs.ITCS.2021,
  title =	{{LIPIcs, Volume 185, ITCS 2021, Complete Volume}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{1--1550},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021},
  URN =		{urn:nbn:de:0030-drops-135381},
  doi =		{10.4230/LIPIcs.ITCS.2021},
  annote =	{Keywords: LIPIcs, Volume 185, ITCS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ITCS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: James R. Lee

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lee:LIPIcs.ITCS.2021.0,
  author =	{Lee, James R.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.0},
  URN =		{urn:nbn:de:0030-drops-135397},
  doi =		{10.4230/LIPIcs.ITCS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.1
Separators in Region Intersection Graphs

Authors: James R. Lee

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
For undirected graphs G=(V,E) and G_0=(V_0,E_0), say that G is a region intersection graph over G_0 if there is a family of connected subsets {R_u \subseteq V_0 : u \in V} of G_0 such that {u,v} \in E \iff R_u \cap R_v \neq \emptyset. We show if G_0 excludes the complete graph K_h as a minor for some h \geq 1, then every region intersection graph G over G_0 with m edges has a balanced separator with at most c_h \sqrt{m} nodes, where c_h is a constant depending only on h. If G additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning. A string graph is the intersection graph of continuous arcs in the plane. String graphs are precisely region intersection graphs over planar graphs. Thus the preceding result implies that every string graph with m edges has a balanced separator of size O(\sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the O(\sqrt{m} \log m) bound of Matousek (2013).
Cite as

James R. Lee. Separators in Region Intersection Graphs. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lee:LIPIcs.ITCS.2017.1,
  author =	{Lee, James R.},
  title =	{{Separators in Region Intersection Graphs}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{1:1--1:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.1},
  URN =		{urn:nbn:de:0030-drops-81970},
  doi =		{10.4230/LIPIcs.ITCS.2017.1},
  annote =	{Keywords: Graph separators, planar graphs, spectral partitioning}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact